﻿#define _CRT_SECURE_NO_WARNINGS

给定一个仅包含数字 2 - 9 的字符串，返回所有它能表示的字母组合。答案可以按 任意顺序 返回。

给出数字到字母的映射如下（与电话按键相同）。注意 1 不对应任何字母。





示例 1：

输入：digits = "23"
输出：["ad", "ae", "af", "bd", "be", "bf", "cd", "ce", "cf"]
示例 2：

输入：digits = ""
输出：[]
示例 3：

输入：digits = "2"
输出：["a", "b", "c"]



//思路：递归，回溯：相当于digits串去遍历，从前往后遍历一个找到它对应的串，可以想象成后面的数字对应的串依次套在前面的
//串里面，也就是多个循环依次相套，即递归
class Solution {

public:
    vector<string>ret;
    string tmp;
    const vector<string>vs = { "abc","def","ghi","jkl","mno","pqrs","tuv","wxyz" };//不能写到函数里：否则另一个将无法识别，故
    //定义在两个函数外部，或者写在里面则利用传参需要扩大backtrack的参数个数
    vector<string> letterCombinations(string digits) {
        int len = digits.size();
        if (len) {
            backtrack(digits, 0);
            return ret;//判空
        }
        else {
            return ret;
        }
    }
    void backtrack(string digits, int pos) {//不能改变原函数参数故创建新的递归函数
        if (pos >= digits.size()) {
            ret.push_back(tmp);
            //tmp.pop_back();这里如果放在这，则它的上上层递归则无法删除被组合完的数据，可能会出现abd等情况
            return;
        }
        int num = digits[pos] - '2';//转化成vs里面对应下标的字母串
        for (auto a : vs[num]) {
            tmp += a;
            backtrack(digits, pos + 1);
            tmp.pop_back();

        }
    }

};






给一个长度为 n 的数组，数组中有一个数字出现的次数超过数组长度的一半，请找出这个数字。
例如输入一个长度为9的数组[1, 2, 3, 2, 2, 2, 5, 4, 2]。由于数字2在数组中出现了5次，
超过数组长度的一半，因此输出2。

数据范围：
�
≤
50000
n≤50000，数组中元素的值
0
≤
�
�
�
≤
10000
0≤val≤10000
要求：空间复杂度：
�
(
    1
)
O(1)，时间复杂度
�
(
    �
)
O(n)
输入描述：
保证数组输入非空，且保证有解



class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param numbers int整型vector
     * @return int整型
     */
    int MoreThanHalfNum_Solution(vector<int>& numbers) {

        int max = numbers[0];
        int min = numbers[0];

        for (int i = 0; i < numbers.size(); i++) {
            if (max <= numbers[i]) {
                max = numbers[i];

            }
            if (min >= numbers[i]) {
                min = numbers[i];

            }

        }
        int* tmp = new int[max - min + 1] {0};

        for (int j = 0; j < numbers.size(); j++) {

            tmp[numbers[j] - min]++;

        }
        //由于是在原数组第一个发现出现次数符合题意就返回，而直接遍历tmp数组可能会把原数组值顺序变了放入tmp；故要按着原数组顺序遍历tmp即可。
        for (int j = 0; j < numbers.size(); j++) {
            if (tmp[numbers[j] - min] > numbers.size() / 2) {
                return numbers[j];

            }
        }


        return 0;
    }

};






给你一个 非严格递增排列 的数组 nums ，请你 原地 删除重复出现的元素，使每个元素 只出现一次 ，返回删除后数组的新长度。元素的 相对顺序 应该保持 一致 。然后返回 nums 中唯一元素的个数。

考虑 nums 的唯一元素的数量为 k ，你需要做以下事情确保你的题解可以被通过：

更改数组 nums ，使 nums 的前 k 个元素包含唯一元素，并按照它们最初在 nums 中出现的顺序排列。nums 的其余元素与 nums 的大小不重要。
返回 k 。

输入：nums = [1, 1, 2]
输出：2, nums = [1, 2, _]
解释：函数应该返回新的长度 2 ，并且原数组 nums 的前两个元素被修改为 1, 2 。不需要考虑数组中超出新长度后面的元素。
示例 2：

输入：nums = [0, 0, 1, 1, 1, 2, 2, 3, 3, 4]
输出：5, nums = [0, 1, 2, 3, 4]
解释：函数应该返回新的长度 5 ， 并且原数组 nums 的前五个元素被修改为 0, 1, 2, 3, 4 。不需要考虑数组中超出新长度后面的元素。






class Solution {
public:
    int removeDuplicates(vector<int>& nums) {
        int max = nums[0];
        int min = nums[0];

        for (int i = 0; i < nums.size(); i++) {
            if (max <= nums[i]) {
                max = nums[i];

            }
            if (min >= nums[i]) {
                min = nums[i];

            }

        }
        int* tmp = new int[max - min + 1] {0};

        for (int j = 0; j < nums.size(); j++) {
            if (tmp[nums[j] - min] == 0) {

                tmp[nums[j] - min]++;
            }

        }
        nums.clear();
        int count = 0;
        for (int k = 0; k < max - min + 1; k++) {
            if (tmp[k] == 1) {
                nums.push_back(k + min);

                count++;
            }
        }
        return count;

    }
};